#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H

#include <vector>
#include <map>
#include "HuffmanNode.h"
#include <string>

/**
 * @class HuffmanTree
 * @brief 表示哈夫曼树及其相关操作。
 *
 * 哈夫曼树是一种用于数据压缩的二叉树，通过字符的权重构造最优编码方案。
 * 本类提供了哈夫曼树的构造和编码生成功能。
 */
class HuffmanTree {
private:
    std::vector<HuffmanNode> tree;               // 哈夫曼树节点列表
    std::map<unsigned char, std::string> encodingMap; // 字节对应的哈夫曼编码

    /**
     * @brief 选择两个权重最小的节点。
     *
     * 从前 n 个节点中选择权重最小的两个节点，其索引分别存储到 s1 和 s2 中。
     * @param n 搜索范围，表示从 0 到 n-1 的节点中进行选择。
     * @param s1 用于存储权重最小节点的索引。
     * @param s2 用于存储权重次小节点的索引。
     */
    void selectTwo(int n, int& s1, int& s2); 

public:
    /**
     * @brief HuffmanTree 的构造函数。
     *
     * 根据给定的字符及其权重初始化哈夫曼树。
     * @param weights 字符与其权重的映射，用于构造哈夫曼树。
     */
    HuffmanTree(const std::map<unsigned char, long long>& weights); 

    /**
     * @brief 构造哈夫曼树并生成编码表。
     *
     * 通过节点权重构造哈夫曼树，并根据树的结构为每个字符生成对应的哈夫曼编码。
     */
    void generateTree(); 

    /**
     * @brief 获取哈夫曼编码表。
     *
     * 返回字符与哈夫曼编码的映射表，用于编码过程。
     * @return 字节与哈夫曼编码的映射。
     */
    const std::map<unsigned char, std::string>& getEncodingMap() const; 

    /**
     * @brief 获取哈夫曼树。
     *
     * 返回哈夫曼树的节点列表，用于调试或其他操作。
     * @return 哈夫曼树的节点列表。
     */
    const std::vector<HuffmanNode>& getTree() const; 
};

#endif // HUFFMANTREE_H
